package com.gitee.ywj1352.leecode;

import org.junit.Test;

import java.util.HashMap;

/**
 * @author wenjie.yang on 2019/9/19.
 */
public class SortSolution {

    /**
     * 快速排序
     *
     * @param arr
     * @param left
     * @param right
     */
    public void quickSort2(int[] arr, int left, int right) {
        int i = left;
        int j = right;
        //给一个 元素 来实现
        int m = arr[(left + right) / 2];
        //交换 找到中间对象 把 大于该 对象的数字 放在右边,小于该 对象的放在 左边
        while (i <= j) {
            while (arr[i] < m) {
                i++;
            }
            while (arr[j] > m) {
                j--;
            }
            if (i <= j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j--;
            }
        }
        //递归的把左边的完成
        if (i < right) {
            quickSort2(arr, i, right);
        }
        //递归的把右边的完成
        if (j > left) {
            quickSort2(arr, left, j);
        }
    }

    @Test
    public void quickSortTest() {
        //int[] arr = {1, 4, 5, 67, 24, 2, 7, 8, 6, 9, 44};
        int[] arr = {3,2,1,9,4};
        quickSort2(arr, 0, 2);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + ",");
        }

    }

    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    //交换
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    @Test
    public void bubbleSort() {
        int[] arr = {9, 3, 5, 1, 2, 6};
        bubbleSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ,");

        }
    }

    /**
     * 选择排序 就是 从头开始找 最小的 依次进入 数组
     *
     * @param arr
     * @return
     */
    public static int[] selectSort(int[] arr) {
        int jmin = Integer.MAX_VALUE;
        int idx = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {
                //arr[j]
                if (arr[j] < jmin) {
                    jmin = arr[j];
                    idx = j;
                }
            }
            int temp = arr[i];
            arr[i] = jmin;
            arr[idx] = temp;
            jmin = Integer.MAX_VALUE;
        }
        return arr;
    }

    @Test
    public void selectSort() {
        int[] arr = {9, 3, 5, 1, 2, 6};
        selectSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ,");
        }
    }


    /**
     * 插入排序
     */
    public static int[] insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            //本质是插入到 第一个比自己小的 地方 每次比较要交换位置
            int now = arr[i];
            for (int j = i; j > 0; j--) {
                if (now >= arr[j - 1]) {
                    continue;
                } else {
                    arr[j] = arr[j - 1];
                    arr[j - 1] = now;
                }
            }
        }
        return arr;
    }

    @Test
    public void insertSort() {
        int[] arr = {9, 3, 5, 1, 2, 6};
        insertSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ,");
        }
    }


    /**
     * 计数排序
     *
     * @param arr
     * @return
     */
    public static int[] countSort(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        int[] countArr = new int[max + 1];
        for (int i = 0; i < arr.length; i++) {
            countArr[arr[i]] += 1;
        }
        for (int i = 0, j = 0; i < countArr.length; i++) {
            while (countArr[i] > 0) {
                arr[j] = i;
                j++;
                countArr[i]--;
            }
        }
        return arr;
    }

    @Test
    public void countSort() {
        int[] arr = {9, 3, 5, 1, 2, 1, 1, 1, 6};
        countSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ,");
        }
    }

    private HashMap map = new HashMap();

    public int fun(int n) {
        if (n == 0) {
            map.put(0, 0);
            return 0;
        }
        if (n == 1) {
            map.put(1, 1);
            return 1;
        }
        if (map.containsKey(n)) {
            return (int) map.get(n);
        } else {
            int r = fun(n - 1) + fun(n - 2);
            map.put(n, r);
            return r;
        }
    }

    @Test
    public void fun1() {
        int fun = fun(3);
        System.out.println(fun);
    }


    public int getMaxW(int[] arr, int[] w, int bw) {
        //设置状态表 并存储 价值
        int[][] s = new int[arr.length][bw + 1];

        for (int i = 0; i < arr.length; i++) {
            //不放入
            for (int j = 0; j < arr.length; j++) {
                if (s[i - 1][j] >= 0)
                    //因为 不放入 背包 所以背包不加如 东西 导致 东西的w 和 上一次的放入
                    //的质量相同
                    s[i][j] = s[i - 1][j];
            }
            //不放入
            for (int j = 0; j < arr.length - arr[i]; j++) {
                if (s[i - 1][j] >= 0)
                    s[i][j+w[i]] = s[i - 1][j] + w[i];
            }
        }

        return 0;
    }


}
